package JZ52_正则表达式匹配;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param pattern string字符串
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
        if (str == null || pattern == null){
            return false;
        }
        return matchCore(str.toCharArray(), 0, pattern.toCharArray(), 0);
    }

    private boolean matchCore(char[] str, int i, char[] pattern, int j) {
        // 若 str 长度和 pattern 长度同时耗尽，则匹配成功
        if (str.length == i && pattern.length == i){
            return true;
        }

        // 若 str 没耗尽， pattern 耗尽，则匹配失败
        if (pattern.length == i && str.length > i){
            return false;
        }

        // 若 str 耗尽，pattern 没耗尽，继续下面的判断（主要为了解决 "" 和 "x*" 这种匹配）
        // 若 str 和 pattern 都没耗尽，继续下面的判断

        // 若 pattern 后面一个字符后面是 *
        if (pattern.length > j + 1 && pattern[j + 1] == '*'){
            // 若 str 当前字符和 pattern 当前字符匹配，三种选择
            if (matchChar(str, i , pattern, j)){
                // -要么 str 不变，将 pattern 后移两位（* 匹配 0 次）
                // -要么将 str 后移一位，pattern 后移两位（* 匹配 1 次）
                // -要么将 str 后移一位，pattern 不变（继续利用 * 匹配）
                return matchCore(str, i, pattern, j + 2)
                        || matchCore(str, i + 1, pattern, j + 2)
                        || matchCore(str, i + 1, pattern, j);

            }else { // 若 str 当前字符和 pattern 当前字符不匹配
                // str 不变，将 pattern 后移两位（* 匹配 0 次）
                return matchCore(str, i, pattern, j + 2);
            }
        }else { // 若 pattern 后面一个字符不是 *
            // 若 str 当前字符和 pattern 当前字符匹配
            if (matchChar(str, i, pattern, j)){
                // 将 str 后移一位，pattern 后移一位
                return matchCore(str, i + 1, pattern, j + 1);
            }
        }
        // 其他情况，返回 false
        return false;
    }

    private boolean matchChar(char[] str, int i, char[] pattern, int j) {
        return i < str.length
                && j < pattern.length
                && (str[i] == pattern[j] || pattern[j] == '.');
    }
}